[2016 MPRI 2.11.1] 1. Introduction to Approximation Algorithms (2016/9/14)

MPRI - Parisian Master of Research in Computer Science <br />Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming <br />Nicolas SCHABANEL, CNRS - Université Paris Diderot <br /> <br />LECTURE 1 (2016/09/14) <br />INTRODUCTION TO APPROXIMATION ALGORITHMS <br /> <br />[0:00:00] 0. Introduction to the Course <br />[0:09:10] 1. Optimization problems & Approximation Algorithms <br />[0:31:24] 2. About Hardness of approximation <br />[1:06:03] 3. Approximation Algorithms for Metric TSP <br />[1:33:28] 4. Exercice: 3/2-Approximation for Metric TSP <br />[2:25:03] 5. Exercise: Maximum Arc-Disjoint Paths (1)